package main.Q801_900;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Q871_880 {
    public static void main(String[] args) {
        System.out.println("Question871：");
        System.out.println("Question872：");
        System.out.println("Question873：最长的斐波那契子序列的长度");
        System.out.println("Question874：");
        System.out.println("Question875：爱吃香蕉的珂珂");
        System.out.println("Question876：链表的中间结点");
        int[] piles={5,3,4,5};
        System.out.println(new Question877().stoneGame(piles));
        System.out.println("Question877：石子游戏");
        System.out.println("Question878：");
        System.out.println("Question879：");
        System.out.println("Question880：");
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

class Question873 {
    public int lenLongestFibSubseq(int[] arr) {
        int max = 0, length = arr.length;
        int[][] dp = new int[length][length];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) map.put(arr[i], i);
        for (int i = 0; i < length; i++) {
            for (int j = i - 1; j >= 0 && arr[j] * 2 > arr[i]; j--) {
                int temp = map.getOrDefault(arr[i] - arr[j], -1);
                if (temp >= 0) dp[j][i] = Math.max(dp[temp][j] + 1, 3);
                max = Math.max(max, dp[j][i]);
            }
        }
        return max;
    }
}

class Question875 {
    public boolean process(int[] piles, int y, long h) {
        long sum = 0;
        for (int x : piles) {
            int count = x / y;
            int temp = x % y == 0 ? 0 : 1;
            sum += count + temp;
        }
        return sum <= h;
    }

    public int minEatingSpeed(int[] piles, int h) {
        Arrays.sort(piles);
        int left = 0, right = piles[piles.length - 1] + 1, result = right;
        while (left + 1 < right) {
            int c = left + (right - left) / 2;
            if (process(piles, c, h)) {
                right = c;
                result = Math.min(result, c);
            } else {
                left = c;
            }
        }
        return result;
    }
}

class Question876 {
    public ListNode middleNode(ListNode head) {
        ListNode fast = head, slow = head;
        if (head.next == null) return head;
        else if (head.next.next == null) return head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

class Question877 {
    public boolean stoneGame(int[] piles) {
        int n = piles.length;
        int[][] dp = new int[n + 2][n + 2];
        for (int len = 1; len <= n; len++) { // 枚举区间长度
            for (int l = 1; l + len - 1 <= n; l++) { // 枚举左端点
                int r = l + len - 1; // 计算右端点
                int a = piles[l - 1] - dp[l + 1][r];
                int b = piles[r - 1] - dp[l][r - 1];
                dp[l][r] = Math.max(a, b);
            }
        }
        return dp[1][n] > 0;
    }
}